#include "iostream"
#include "vector"

using namespace std;

void heapConstruct(vector<int> &heap, int i, int length)
{
    // 根据给定的完全二叉树中的某个结点,调整以该结点为根节点的树的各个节点,让大的元素在前头;即让这个子树满足大顶堆的要求
    int temp = heap[i - 1]; // 即当前给定的这个节点,也就是当前的根节点
    int j;
    for (j = 2*i; j <= length; j=j*2) // 同样,这里j也认为是数字下标+1
    {
        if (j < length && heap[j - 1] < heap[j]) // j < length防止只有左孩子,没有右孩子
        {
            // i的左右孩子进行比较;只关注那个大的孩子
            j++;
        }
        if (temp > heap[j - 1])
        {
            // 这是父结点比较大的孩子结点还要大,那么说明以父结点为根节点的这个树就是大顶堆;
            break;
        }
        // 否则需要将父结点与较大的孩子结点交换,让最大的作为根结点
        heap[i - 1] = heap[j - 1];
        i = j; // 下次循环的根结点变成当前较大的那个孩子结点;因为这俩交换了,所以可能会使得以这个较大孩子结点为根节点的子树不满足大顶堆的要求
    }
    heap[i - 1] = temp; // 没交换时i没变;如果交换了,i最终位于换上去的那个数原来的那位置
}
// 构建大顶堆的测试
void max_heap(vector<int> &heap)
{
    // 将无序的数组变成最大堆;堆是一个完全二叉树的结构,根据完全二叉树的性质,这里使用数组来存放最大堆
    for (int i = heap.size() / 2; i > 0; i--) // 
    {
        // 由于下标从1开始的完全二叉树父子节点之间存在2i和2i+1的关系;但是数组下标是从0开始的,所以要注意;
        // 也正因为这样的编号特点,这里的循环从heap.size() / 2开始是因为完全二叉树最后一个叶子节点的父节点是heap.size() / 2;
        heapConstruct(heap, i, heap.size()); // 这里的i就不是数组下标了;数组下标=i-1
    }
}
// 堆排序
void max_heap2(vector<int> &heap)
{
    // 将无序的数组变成最大堆;堆是一个完全二叉树的结构,根据完全二叉树的性质,这里使用数组来存放最大堆
    for (int i = heap.size() / 2; i > 0; i--)
    {
        // 由于下标从1开始的完全二叉树父子节点之间存在2i和2i+1的关系;但是数组下标是从0开始的,所以要注意;
        heapConstruct(heap, i, heap.size()); // 这里的i就不是数组下标了;数组下标=i-1
    }
    // 借助大顶堆进行排序
    for (int i = heap.size(); i > 1; i--) // 这里的i也是下标+1
    {
        swap(heap[0], heap[i - 1]); // 每次将大顶堆堆顶元素放到最后;因此这是升序;
        // 每次调整都是调整堆顶的那个节点,即1;数组的长度也就是i-1;
        heapConstruct(heap, 1, i - 1); // 这里调整大顶堆时需要处理的就是堆的根结点,因为此时堆顶元素肯定比两个孩子结点中较大的那个要小;加速也是这里加速;因为只需要调整一侧;
    }
}

int main()
{
    // 给一个无序的数组
    vector<int> a = {3, 8, 7, 9, 0, 3, 1, 2};
    // 输出初始的无序数组
    for (int i = 0; i < a.size(); i++)
    {
        cout << a[i] << " ";
    }

    cout << endl;
    // 输出符合大顶堆要求的数组
    // max_heap(a);
    // for (int i = 0; i < a.size(); i++)
    // {
    //     cout<<a[i]<<" ";
    // }
    // 输出堆排序结果(升序)
    max_heap2(a);
    for (int i = 0; i < a.size(); i++)
    {
        cout << a[i] << " ";
    }

    cout << endl;

    return 0;
}